package graph;

import java.util.ArrayDeque;
import java.util.Deque;

public class numIslands {
    public int numIslands(char[][] grid) {
        int x = grid.length, y = grid[0].length;
        boolean[][] mark = new boolean[x][y];

        int count = 0;
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (grid[i][j] == '1' && !mark[i][j]) {
                    bfs(i, j, mark, grid);
                    count++;
                }
            }
        }
        return count;
    }

    public void bfs(int x, int y, boolean[][] mark, char[][] grid) {
        Deque<int[]> queue = new ArrayDeque();
        queue.offer(new int[] { x, y });
        mark[x][y] = true;

        while (!queue.isEmpty()) {
            int[] point = queue.poll();
            int row = point[0];
            int col = point[1];
            if (row - 1 >= 0 && grid[row - 1][col] == '1' && !mark[row - 1][col]) {
                queue.offer(new int[] { row - 1, col });
                mark[row-1][col] = true;

            }
            if (row + 1 < grid.length && grid[row + 1][col] == '1' && !mark[row + 1][col]) {
                queue.offer(new int[] { row + 1, col });
                mark[row+1][col] = true;

            }
            if (col - 1 >= 0 && grid[row][col - 1] == '1' && !mark[row][col - 1]) {
                queue.offer(new int[] { row, col - 1 });
                mark[row][col-1] = true;

            }
            if (col + 1 < grid[0].length && grid[row][col + 1] == '1' && !mark[row][col + 1]) {
                queue.offer(new int[] { row, col + 1 });
                mark[row][col+1] = true;

            }
        }
    }

    public static void main(String[] args) {
        // char[][] grid = new char[][] {
        // { '1', '1', '0', '0', '0' },
        // { '1', '1', '0', '0', '0' },
        // { '0', '0', '1', '0', '0' },
        // { '0', '0', '0', '1', '1' }
        // };
        char[][] grid = new char[][] {
                { '1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '0', '1', '0', '1', '1' },
                { '0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '1', '0' },
                { '1', '0', '1', '1', '1', '0', '0', '1', '1', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
                { '1', '1', '1', '1', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
                { '1', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
                { '1', '0', '1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '0', '1', '1', '1', '0', '1', '1', '1' },
                { '0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '0', '1', '1', '1', '1' },
                { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '0', '1', '1' },
                { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
                { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
                { '0', '1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
                { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
                { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
                { '1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '1', '1' },
                { '1', '0', '1', '1', '1', '1', '1', '0', '1', '1', '1', '0', '1', '1', '1', '1', '0', '1', '1', '1' },
                { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '1', '1', '0' },
                { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '0', '0' },
                { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
                { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
                { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' }
        };
        numIslands item = new numIslands();
        System.out.println(item.numIslands(grid));
    }
}
